#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#		"End of shell archive."
# Contents:  perf.c
# Wrapped by oz@yunexus on Fri Dec 14 12:08:56 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'perf.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'perf.c'\"
else
echo shar: Extracting \"'perf.c'\" \(29699 characters\)
sed "s/^X//" >'perf.c' <<'END_OF_FILE'
X
X/*
X *			P e r f e c t   H a s h
X *
X *
X *	Program to search for Minimal Perfect Hash Functions for
X *	use in lexical analyzers. C.D. Havener Jan 26 1982
X *	GenRad Inc. 37 Great Road, Bolton Mass. 01740
X *	Based on paper "Minimal Perfect Hash Functions Made Simple"
X *	by Richard J. Cichelli - Comm. of ACM Jan 1980 pp 17-19
X *
X *	Synopsis: The hash function is h = assoc value of 1st
X *	letter + length of keyword + assoc value of last letter
X *
X *	This program finds the associated values of the letters
X *	given a list of keywords, 1 per line. It works most of
X *	the time for up to about 40 keywords but certain
X *	pathological cases exist. A semi-perfect hash is usually
X *	found by the program. The user can then tighten the
X *	default limits for max associated char value or the
X *	table limit using the -v and -t options. Sometimes the
X *	presort heuristics actually make the search process
X *	much more difficult. The user can try his luck at manual
X *	sorting using the -n option. Since the hash function
X *	produces such a limited range of numbers it can only work
X *	for up to about 40 keywords. If a language needs say 80
X *	keywords just split them up into two tables and let the
X *	lexical analyzer look in first one then the other, this
X *	will still be much faster than any other keyword lookup.
X *
X *	This program has run sucessfully on a VAX 11/780 under
X *	4.1BSD and VMS (using Vax-11 C and Decus C).
X */
X
X/*)BUILD
X	$(MP) = 1			# uses macros with arguments
X	$(STACK)	= 10000		# lots of recursion
X	$(TKBOPTIONS)	= {
X	    STACK	= 1024
X	    TASK	= ...PRF
X	}
X*/
X
X#ifdef	DOCUMENTATION
Xtitle	perfect		Find Perfect Hash Functions
Xindex	perfect		Find perfect hash functions
X
Xsynopsis
X
X	perfect [-options]
X
Xdescription
X
X	perfect reads a list of keywords from the standard input
X	and computes a "perfect hash" function for the set.
X	The following options are defined:
X	.lm +8
X	.s.i -8;-d######Enable debug code.
X	.s.i -8;-n######Disable pre-sort of keywords.  (See below).
X	.s.i -8;-t#<n>##Limit the maximum table size to <n> entries.
X	.s.i -8;-v#<n>##Limit the maximum associated character value.
X	.s.i -8;-k#<n>##Use only the first <n> keywords in the list.
X	.s.i -8;-a#<n>##Give a status report every <n> seconds.
X	(Unix and Vax-11C/VMS only).
X	.s.i -8;-o#file#Write a sample keyword lookup routine to the
X	indicated file.
X	.s.lm -8
X	The program prints a running commentary on the standard
X	output.
X
XAuthor
X
X	Charlie Havener, GenRad Inc.  Bolton Mass.
X
X	(Modified by Martin Minow, Dec, Maynard Mass.)
X
XDiscussion
X
X	This technical note describes an implementation of a
X	pragmatic algorithm for finding perfect or semi-perfect hash
X	functions for lists of keywords. The resulting hash function can
X	be used to speed up lexical analyzers used in translators and
X	compilers. The algorithm was described by R.J. Cichelli in The
X	January 1980 issue of Communications of the ACM under the title
X	"Minimal Perfect Hash Functions made Simple." The article did not
X	include a computer language description of the algorithm and some
X	important implementation details were unclear. It is assumed that
X	the user will know what to do with the output of this program.
X	The -o option may be used to produce a lexical analyser kernel
X	from the tables built by this program. Another reference for
X	those wishing to pursue the topic further is "More On Minimal
X	Perfect Hash tables" by Curtis Cook and R. Oldehoeft, a Colorado
X	State University Technical Report.
X
X	The program takes a list of keywords and sorts them in such
X	a way that the search time for a hash function will be
X	reasonable. Once sorted a recursive trial and error procedure
X	hunts for a hash function satisfying user supplied bounds
X	of table size and associated character value limits.  The
X	built-in hash function is
X
X	    hash = assoc value of first character
X		+ keyword length
X		+ assoc value of last character
X
X	It is critically important to select a good ordering of the
X	keywords before searching begins. I ran up 100 hours of VAX time
X	searching for a hash function with an unordered list, and gave
X	up. Once the sort heuristics were debugged it found the hash
X	function in minutes. Typically it will find the function in
X	minutes or you may as well give up. A status reporting feature is
X	built into the program on the UNIX system that lets you follow
X	the progress of the search depth. If it has trouble, you can
X	tell just which word it can't get past, and take appropriate
X	action. If it has trouble you can attempt to alter its choice of
X	pre-ordering by moving troublesome words to the front of the
X	list. In a sequel to his paper, Cichelli stated that sometimes
X	the sort heuristics makes the search longer. There is also no
X	guarantee that a hash function can be found. The program does the
X	obvious precheck that no two keywords have the same first and
X	last letter and length in common (e.g. BAK KAB). Nonetheless,
X	as pointed out by Jaeschke and Osterberg in an overly harsh
X	criticism, there are many pathological sets of keywords that fail.
X	(On Cichelli's minimal perfect hash functions method. Comm. ACM
X	Dec. 1980, pp 728-729) The algorithm also only works for up to
X	about 40 keywords due to the limited range of numbers the formula
X	can generate. If you have, say 80 keywords, just make two hash
X	tables and look in each one. Here are some examples of the
X	program's output:
X	.s.nf
X	Perfect hash function finder, CDH Ver. 2.9
X	Start time = Mon Oct 17 20:40:40 1983
X	28 keywords, 19 distinct letters.
X	The associated char value limit is 19
X	The table size limit is 100
X	The search ordering is
X	 else double continue case float struct sizeof
X	 static short extern typedef default register for
X	 char while entry int if return do unsigned switch
X	 union goto auto long break
X	.s
X	Success! Associated Char Values Follow:
X	 a =19, b = 4, c = 1, d = 0, e = 0, f = 3, g =17,
X	 h =14, i =17, k =19, l = 6, n = 8, o = 0, r =11,
X	 s = 6, t = 0, u =16, w =13, y =14,
X	Hash min = 2, max = 30, spread = 29
X	 do 2, else 4, case 5, double 6, default 7,
X	 float 8, continue 9, typedef 10, short 11, struct 12,
X	 static 13, extern 14, sizeof 15, char 16, for 17,
X	 while 18, entry 19, int 20, goto 21, if 22, auto 23,
X	 unsigned 24, return 25, switch 26, long 27, break 28,
X	 union 29, register 30,
X	.s
X	Total search() invocations = 15913
X	 Started Mon Oct 17 20:40:40 1983
X	Finished Mon Oct 17 20:40:42 1983
X	.s.nf
X	Perfect hash function finder, CDH Ver. 2.9
X	Start time = Mon Oct 17 20:41:11 1983
X	39 keywords, 19 distinct letters.
X	The associated char value limit is 19
X	The table size limit is 100
X	The search ordering is
X	 TEXT RESET TRUE REWRITE READLN SQRT SQR EOLN TRUNC
X	 PUT EXP PAGE CHR CHAR COS SUCC READ ROUND DISPOSE
X	 PRED SIN OUTPUT ORD INPUT INTEGER GET MAXINT REAL
X	 WRITE EOF FALSE NEW WRITELN LN ARCTAN ABS BOOLEAN
X	 PACK UNPACK
X	.s
X	Success! Associated Char Values Follow:
X	 A =18, B =11, C =16, D =18, E = 3, F = 3, G = 0,
X	 I = 1, K =19, L = 9, M =18, N =19, O = 8, P = 9,
X	 R = 0, S =14, T = 0, U =13, W =19,
X	Hash min = 3, max = 45, spread = 43
X	 GET 3, TEXT 4, RESET 5, INPUT 6, TRUE 7,
X	 INTEGER 8, EOF 9, REWRITE 10, FALSE 11, PUT 12,
X	 REAL 13, OUTPUT 14, EXP 15, PAGE 16, SQR 17, SQRT 18,
X	 CHR 19, CHAR 20, TRUNC 21, READ 22, ROUND 23,
X	 MAXINT 24, READLN 25, EOLN 26, WRITE 27, DISPOSE 28,
X	 ORD 29, LN 30, PRED 31, PACK 32, COS 33, SUCC 34,
X	 ABS 35, SIN 36, BOOLEAN 37, UNPACK 38, NEW 41,
X	 ARCTAN 43, WRITELN 45,
X	.s
X	Total search() invocations = 149292
X	 Started Mon Oct 17 20:41:11 1983
X	Finished Mon Oct 17 20:41:35 1983
X	.s 2.f
X	Usually, the first time you run perf, just let everything
X	default. The second time,
X	use the -t option to limit the table size to the first hash
X	value plus the number of keywords.
X
X	On Unix and Vax/VMS (Vax-11 C), The program will accept
X	SIGTERM signals (CTRL/C on VMS) for an update status report
X	since it may take quite a while to find the hash function values.
X
XSample keyword tables
X
X	The following tables are known to work correctly.
X	The first defines the keywords for the C programming
X	language; the second for a toy computer language.
X
X	int char float double struct union long short
X	unsigned auto extern register typedef static
X	goto return sizeof break continue if else for
X	do while switch case default entry
X
X	GET TEXT RESET OUTPUT MAXINT INPUT TRUE
X	INTEGER EOF REWRITE FALSE CHR CHAR TRUNC REAL
X	SQR SQRT WRITE PUT ORD READ ROUND READLN EXP
X	PAGE EOLN COS SUCC DISPOSE NEW ABS LN BOOLEAN
X	WRITELN SIN PACK UNPACK ARCTAN PRED
X
X#endif
X
X#include	<stdio.h>
X#include	<ctype.h>
X
X#define	EOS	'\0'
X#define	FALSE	0
X#define	TRUE	1
X#define	VOID	int
X
X#ifdef	unix
X#define	UNIX	1
X#define	DOALARM	1
X#endif
X
X#ifndef	vms
X#define	VMS	0
X#else
X#define	VMS	1
X#define	DOALARM	1
X#endif
X
X#ifndef	UNIX
X#define	UNIX	0
X#endif
X
X#ifndef	DOALARM
X#define	DOALARM	0
X#endif
X
X#if	UNIX
X#define	IO_ERROR	1
X#endif
X
X#if	VMS
X#include	<ssdef.h>
X#define	IO_ERROR	SS$_ABORT
X/*
X * This creates text files in vanilla RMS on VMS
X */
Xextern FILE	*fdopen();
X#define	CREATE(f, m) fdopen(creat(f, 0, "rat=cr", "rfm=var"), m)
X#else
X#define	CREATE	fopen
X#endif
X
X#if	DOALARM
X#include	<signal.h>
Xextern int	status();
X#endif
X
X#define	MAXKEYS		100		/* Maximum number of keys	*/
X#define MAXCHARS	0377		/* Maximum number of char's	*/
X#define UNDEF		-1		/* the undefined value		*/
X
Xtypedef struct keyword {
X    int		len;		/* Keyword length			*/
X    char	last;		/* Last byte of keyword			*/
X    char	word[1];	/* Keyword text				*/
X} KEYWORD;
X
X/*
X * Define some frequently used operations as macros:
X *	hash(p)		returns the hash value for this keyword
X *	used(n)		TRUE if this hash value is in use or illegal
X *	defined(c)	TRUE if this character is defined
X */
X
X#define hash(p)		(value[p->word[0]] + p->len + value[p->last])
X#define	used(n)		((n > tablesize || n < 0) ? TRUE : mapped[n])
X#define	defined(c)	(c != UNDEF)
X
Xchar	cval[MAXCHARS];		/* All possible characters		*/
Xshort	cused[MAXCHARS];	/* count of often char used		*/
Xshort	order[MAXKEYS];		/* ordering of key words by subscript	*/
Xshort	neworder[MAXKEYS];	/* the new supposedly improved ordering	*/
Xshort	hashval[MAXKEYS];	/* current hashvalue of the key word	*/
Xshort	value[MAXCHARS];	/* associated value of the character	*/
Xint	mapped[MAXKEYS];	/* track which table entries are in use	*/
Xchar	name[50];		/* bigger than any keyword should be	*/
X
X
XKEYWORD		*keywds[MAXKEYS];
X
Xextern long	time();
Xextern char	*ctime();
Xextern char	*malloc();
Xextern int	aredefined();
Xextern char	*strchr();
X
Xint	debug		= 0;
Xint	nkeys		= sizeof(keywds) / (sizeof (KEYWORD));
Xint	tablesize	= sizeof(keywds) / (sizeof (KEYWORD));
Xshort	trys		= 0;
Xint	nletters	= 0;
Xshort	kilotrys	= 0;
Xint	atime		= 10 * 60;	/* default alarm status 10 min.	*/
Xchar	*klimit		= NULL;
Xchar	*textp		= NULL;
Xlong	bigcount	= 0;
Xshort	depth		= 0;
Xshort	k_now		= 0;		/* value of k for status report	*/
Xint	nosort		= FALSE;	/* -n sets nosort TRUE		*/
Xlong	start, stop;			/* the start and finish times	*/
Xshort	vlimit		= 0;
Xshort	keylimit	= 0;
Xshort	tlimit		= 0;
Xchar	*output		= NULL;		/* Output file if set		*/
X
Xchar	letters[37];			/* string of defined chars	*/
Xchar	*letend = letters;		/* -> free space in letters[]	*/
X
Xmain(argc,argv)
Xint		argc;
Xchar		*argv[];
X{
X	getoptions(argc, argv);
X	start = time(NULL);
X#if	DOALARM
X	signal(SIGALRM,status);
X	signal(SIGTERM,status);		/* status on kill -TERM pid	*/
X	alarm(atime);			/* status every N secs		*/
X#endif
X	setup();
X	dosort();
X	printf("The search ordering is\n");
X	prntorder();
X	if (search(0)) {
X#if	DOALARM
X	    alarm(0);
X#endif
X	    printf("\nSuccess! Associated Char Values Follow:\n");
X	    prntvals();
X	    prnthash();
X	    printf("\n");
X	    if (output != NULL)
X		dooutput();
X	}
X	else {
X#if	DOALARM
X	    alarm(0);
X#endif
X	    printf("\nFailed to find char values for hash function\n");
X	}
X	printf("Total search invocations = %ld, max depth = %d\n",
X	    bigcount, depth);
X	stop = time(NULL);
X	printf(" Started %s", ctime(&start));
X	printf("Finished %s", ctime(&stop));
X}
X
Xsetup()
X{
X	register KEYWORD	*kp;
X	register int		c;
X	register int		i;
X	int			len;
X
X	for (i = 0; (scanf("%s", name)) != EOF; i++) {
X	    if (i >= MAXKEYS) {
X		printf("Too many keys, %d max.\n", MAXKEYS);
X		exit(IO_ERROR);
X	    }
X	    len = strlen(name);
X	    kp = (KEYWORD *) malloc(sizeof (KEYWORD) + len);
X	    if (kp == NULL) {
X		printf("Out of room allocating keywords\n");
X		exit(IO_ERROR);
X	    }
X	    keywds[i] = kp;
X	    kp->len = len;
X	    kp->last = name[len - 1];
X	    strcpy(&kp->word[0], name);
X	}
X	nkeys = (keylimit == 0) ? i : keylimit;
X
X	for (i = 0; i < MAXKEYS; i++) {
X	    hashval[i] = UNDEF;
X	    order[i] = i;
X	    mapped[i] = FALSE;
X	}
X
X	for (i = 0; i < MAXCHARS; i++) {
X	    cval[i] = 0;
X	    value[i] = UNDEF;
X	}
X
X	if (!precheck()) {
X	    printf("Perfect hash search terminated\n");
X	    exit(IO_ERROR);
X	}
X
X	for (i = 0; i < nkeys; i++) {
X	    c = keywds[i]->word[0];	/* Get first char of keyword	*/
X	    cval[c] = c;		/* Remember this one used	*/
X	    if (cused[c] == 0)		/* If it's the first time,	*/
X		++nletters;		/* Count unique letters		*/
X	    ++cused[c];			/* count how often letter used	*/
X	    c = keywds[i]->last;	/* Get last char of keyword	*/
X	    cval[c] = c;		/* And do the same for it	*/
X	    if (cused[c] == 0)
X		++nletters;
X	    ++cused[c];
X	}
X
X	tablesize = (tlimit == 0 ? MAXKEYS : tlimit);
X	printf("Perfect hash function finder, CDH Ver. 2.9\n");
X	printf("Start time = %s", ctime(&start));
X	printf("%d keywords, %d distinct letters.\n",
X	    nkeys, nletters);
X	nletters = (vlimit > 0) ? vlimit : nletters;
X	printf("The associated char value limit is %d\n", nletters);
X	printf("The table size limit is %d\n", tablesize);
X
X	/*
X	 * You should make tablesize at least nkeys + 1 since the
X	 * first value is usually 1 or 2 even if both assoc char
X	 * values are zero since the keyword length is included!
X	 */
X}
X
Xdosort()
X{
X	register KEYWORD	*kp;
X	register int		i, j;
X	int			k, m;
X	int			newvalues;
X
X	if (nosort) {
X	    printf("No presorting of keywords.\n");
X	    return;
X	}
X
X	/*
X	 * first order by sum of frequencies of occurrences of each
X	 * keys 1st and last letter
X	 */
X
X	for (i = 0; i < nkeys; i++) {
X	    kp = keywds[i];
X	    order[i] = cused[kp->word[0]] + cused[kp->last];
X	}
X	for (m = 0; m < nkeys; m++) {
X	    for (k = -1, i = 0; i < nkeys; i++) {
X		if (order[i] > k) {
X		    k = order[i];
X		    j = i;		/* remember keywd subscript	*/
X		}
X	    }
X	    order[j] = 0;
X	    neworder[m] = j;
X	}
X	for (i=0; i < nkeys; i++)
X	    order[i] = neworder[i];
X	if (debug > 2) {
X	    printf("After first ordering\n");
X	    prntorder();
X	}
X
X	/*
X	 * The second ordering follows, keywds whose values are
X	 * defined by keywds earlier in the order are placed
X	 * immediately after they are defined. This causes hash
X	 * value conflicts to occur as early during the search
X	 * as possible.
X	 */
X
X	letend = letters;
X	letters[0] = EOS;
X	merge(order[0]);			/* prime the pump	*/
X	neworder[0] = order[0];
X	order[0] = UNDEF;
X	for (i = 1; i < nkeys;) {
X	    for (newvalues = TRUE; newvalues;) {
X		newvalues = FALSE;
X		for (k = 0; k < nkeys; k++) {
X		    if (order[k] == UNDEF)
X			continue;
X		    if (aredefined(order[k])) {
X			neworder[i++] = order[k];
X			order[k] = UNDEF;
X			continue;
X		    }
X		}
X		for (k = 0; k < nkeys; k++) {
X		    if (order[k] != UNDEF) {
X			neworder[i++] = order[k];
X			merge(order[k]);
X			order[k] = UNDEF;
X			newvalues = TRUE;
X			break;
X		    }
X		}
X	    }
X	}
X	for (i = 0; i < nkeys; i++)
X	    order[i] = neworder[i];
X	if (precheck() == FALSE) {
X	    printf("OOPS - call a Guru, the presort botched it\n");
X	    prntorder();
X	    exit(IO_ERROR);
X	}
X}
X
X/*
X * merge - adds keywd letters to the string of those defined.
X * This could be speeded up, but it's not a critical-path function.
X */
X
XVOID
Xmerge(n)
Xint		n;
X{
X	register KEYWORD	*kp;
X
X	kp = keywds[n];
X	if (debug > 2)
X	    printf("merging in %s\n", kp->word);
X	if (strchr(letters, kp->word[0]) == NULL) {
X	    *letend++ = kp->word[0];
X	    *letend = EOS;
X	}
X	if (strchr(letters, kp->last) != NULL) {
X	    *letend++ = kp->last;
X	    *letend = EOS;
X	}
X}
X
X/*
X * aredefined - see if 1st & last char of keywd are defined
X */
X
Xint
Xaredefined(n)
Xint		n;
X{
X	register KEYWORD	*kp;
X
X	kp = keywds[n];
X	if (strchr(letters, kp->word[0]) != NULL
X	 && strchr(letters, kp->last) != NULL)
X	    return (TRUE);
X	else return (FALSE);
X}
X
X/*
X * precheck - all keywds length,1st and last char disjoint
X */
X
Xint
Xprecheck()
X{
X	int			pretest;
X	register KEYWORD	*ip, *jp;
X	short			i, j;
X	short			m, k;
X	char			a, b;
X
X	pretest = TRUE;
X	for (m = 0; m < nkeys; m++) {
X	    i = order[m];
X	    ip = keywds[i];
X	    a = ip->word[0];
X	    b = ip->last;
X	    for (k = m + 1; k < nkeys-1; k++) {
X		j = order[k];
X		jp = keywds[j];
X		if (ip->len == jp->len
X		 && ((a == jp->word[0] && b == jp->last)
X		  || (a == jp->last && b == jp->word[0]))) {
X		    pretest = FALSE;
X		    printf("Precheck fails on %s and %s\n",
X			ip->word, jp->word);
X		}
X	    }
X	}
X	return (pretest);
X}
X
X/*
X * prntorder - printout the current order of the keywords
X */
X
XVOID
Xprntorder()
X{
X	register int	i, j;
X
X	for (i = 0, j = 0; i < nkeys; i++) {
X	    if ((j + keywds[order[i]]->len) >= 60) {
X		printf("\n");
X		j = 0;
X	    }
X	    printf(" %s", keywds[order[i]]->word);
X	    j += keywds[order[i]]->len + 1;
X	}
X	printf("\n");
X}
X
X/*
X * prntvals - prints out the letter associated values
X */
X
Xprntvals()
X{
X	register int	i, j;
X
X	for (i = 0, j = 0; i < MAXCHARS; i++) {
X	    if (cval[i]) {
X		printf("%s %c =%2d,",
X		    ((++j % 10) == 0) ? "\n" : "",
X		    cval[i], value[i]);
X	    }
X	}
X	printf("\n");
X}
X
X/*
X * prnthash - prints out the hash values for the keywds
X */
X
XVOID
Xprnthash()
X{
X	register int		i, j;
X	register KEYWORD	*kp;
X	int			swap;
X	int			hmin;
X	int			hmax;
X	int			spread;
X
X
X	swap = TRUE;
X	hmin = MAXKEYS;
X	hmax = 0;
X	spread = 0;
X	for (i = 0; i < nkeys; i++) {
X	    j = hashval[i] = hash(keywds[i]);
X	    hmin = (hmin < j) ? hmin : j;
X	    hmax = (hmax > j) ? hmax : j;
X	    order[i] = i;
X	}
X	while (swap) {		/* plain vanilla bubble sort */
X	    swap = FALSE;
X	    for (i = 0; i < nkeys-1; i++) {
X		if (hashval[order[i+1]] < hashval[order[i]]) {
X		    swap = TRUE;
X		    j = order[i];
X		    order[i] = order[i+1];
X		    order[i+1] = j;
X		}
X	    }
X	}
X	printf("Hash min = %d, max = %d, spread = %d\n",
X	    hmin, hmax, hmax - hmin + 1);
X	for (i=0, j=0; i < nkeys; i++, j++) {
X	    kp = keywds[order[i]];
X	    if (j  + (kp->len + 5) > 60) {
X		printf("\n");
X		j = 0;
X	    }
X	    printf(" %s %d,", kp->word,
X		hash(keywds[order[i]]));
X	    j += (kp->len + 5);
X	}
X	printf("\n");
X}
X
X/*
X * search - calls itself recursively to find char values
X */
X
Xint
Xsearch(k)
Xregister int	k;
X{
X	register KEYWORD	*p;
X	register int		j;
X	int			m;
X	short			v1, v2, num;
X	short			sub1, sub2, subn;
X	int			thesame;
X
X	thesame = FALSE;
X	bigcount++;
X	k_now = k;			/* global for status reporting	*/
X	if (k >= nkeys)			/* hey - we may be all done	*/
X	    return (TRUE);
X	if (k > depth)			/* global for status reporting	*/
X	    depth = k;			/* keep track of search depth	*/
X	m = order[k];
X	p = keywds[m];
X	sub1 = p->word[0];		/* sub1 = first letter in word	*/
X	sub2 = p->last;			/* sub2 = last letter in word	*/
X	if (sub1 == sub2)
X	    thesame = TRUE;
X	v1 = value[sub1];
X	v2 = value[sub2];
X	if (defined(v1) && defined(v2)) {
X	    num = hash(p);		/* Both letters defined		*/
X	    if (used(num))
X		return (FALSE);		/* this hash value is in use	*/
X	    else {
X		hashval[m] = num;	/* install it			*/
X		mapped[num] = TRUE;
X		if (search(k + 1))
X		    return (TRUE);
X		else {
X		    hashval[m] = UNDEF;
X		    mapped[num] = FALSE;
X		    return (FALSE);
X		}
X	    }
X	}
X	else if (defined(v1)) {
X	    for (j = 0; j <= nletters; j++) {
X		v2 = j;
X		num = v1 + p->len + v2;
X		if (!used(num)) {
X		    hashval[m] = num;
X		    mapped[num] = TRUE;
X		    value[sub2] = v2;
X		    subn = sub2;
X		    if (search(k + 1))
X			return (TRUE);
X		    else
X			remove(m, sub2);
X		}
X	    }
X	    return (FALSE);
X	}
X	else if (defined(v2)) {
X	    for (j = 0; j <= nletters; j++) {
X		v1 = j;
X		num = v1 + p->len + v2;
X		if (!used(num)) {
X		    hashval[m] = num;
X		    mapped[num] =TRUE;
X		    value[sub1] = v1;
X		    subn = sub1;
X		    if (search(k + 1))
X			return (TRUE);
X		    else
X			remove(m, sub1);
X		}
X	    }
X	    return (FALSE);
X	}
X	else {				/* neither defined		*/
X	    for (j = 0; j <= nletters; j++) {
X		if (thesame) {
X		    v1 = v2 = j;
X		    num = v1 + p->len + v2;
X		    if (!used(num)) {
X			hashval[m] = num;
X			mapped[num] = TRUE;
X			value[sub1] = v1;	/* same as value[sub2]	*/
X			subn = sub1;
X			if (search(k + 1))
X			    return (TRUE);
X			else
X			    remove(m, subn);
X		    }
X		}
X		else {
X		    value[sub1] = j;
X		    if (search(k))		/* if never TRUE thru	*/
X			return (TRUE);		/* for loop, then FALSE */
X		    else
X			value[sub1] = UNDEF;
X		}
X	    }
X	    return (FALSE);
X	}
X}
X
X/*
X * remove - backup by deleting keywds hash value etc
X */
X
XVOID
Xremove(m, subn)
Xregister short	m;
Xregister short	subn;
X{
X	if (debug > 6)
X	    printf("removing %s, subn = %d\n", keywds[m]->word, subn);
X	mapped[hashval[m]] = FALSE;
X	hashval[m] = UNDEF;
X	value[subn] = UNDEF;
X}
X
X/*
X * dooutput writes parser tables to the indicated output file.
X */
X
Xchar	*function[] = {
X	"",
X	"int",
X	"keyword(text)",
X	"register char\t*text;",
X	"/*",
X	" * Look for keyword (string of alpha) in the perfect hash table",
X	" * Return the index (L_xxx value) or 0 if not found",
X	" */",
X	"{",
X	"\tregister char\t*tp;",
X	"\tregister int\thash;",
X	"",
X	"\tif (*text < FIRST || *text > LAST)",
X	"\t    return (0);",
X	"\tfor (tp = text; isalpha(*tp); tp++)",
X	"\t    ;",
X	"\thash = (tp - text);",
X	"\tif (*--tp < FIRST || *tp > LAST)",
X	"\t    return (0);",
X	"\thash += (px_assoc - FIRST)[*text] + (px_assoc - FIRST)[*tp];",
X	"\tif (px_table[hash] == NULL)",
X	"\t    return (0);",
X	"\tif (strncmp(text, px_table[hash], (tp - text + 1)) != 0)",
X	"\t    return (0);",
X	"\treturn(hash);",
X	"}",
X	"",
X	NULL,
X};
X
Xdooutput()
X{
X	FILE		*fd;
X	register char	**funp;
X	register int	i;
X	int		first, last, hval;
X
X	if ((fd = CREATE(output, "w")) == NULL) {
X	    perror(output);
X	    return;
X	}
X	fprintf(fd, "#include <stdio.h>\n");
X	fprintf(fd, "#include <ctype.h>\n");
X	for (i = 0; i < nkeys; i++) {
X	    fprintf(fd, "#define\tL_%s\t", keywds[order[i]]->word);
X	    if (keywds[order[i]]->len < 14)
X		putc('\t', fd);
X	    if (keywds[order[i]]->len <  6)
X		putc('\t', fd);
X	    fprintf(fd, "%d\n",	hash(keywds[order[i]]));
X	}
X	for (i = MAXCHARS; --i >= 0 && cval[i] == 0;)
X	    ;
X	last = i;
X	for (i = 0; i <= last && cval[i] == 0;)
X	    i++;
X	first = i;
X	fprintf(fd, "#define FIRST\t'%c'\n", first);
X	fprintf(fd, "#define LAST\t'%c'\n", last);
X	fprintf(fd, "static char px_assoc[] = {\n");
X	while (i <= last) {
X	    fprintf(fd, "\t%d,\t/* '%c' */\n", value[i], i);
X	    i++;
X	}
X	fprintf(fd, "};\n");
X	fprintf(fd, "static char *px_table[] = {\n");
X	last = 0;
X	for (i = 0; i < nkeys; i++) {
X	    hval = hash(keywds[order[i]]);
X	    while (last < hval) {
X		fprintf(fd, "\tNULL,\t\t\t/*%3d\t*/\n", last);
X		last++;
X	    }
X	    fprintf(fd, "\t\"%s\",\t", keywds[order[i]]->word);
X	    if (keywds[order[i]]->len < 13)
X		putc('\t', fd);
X	    if (keywds[order[i]]->len <  5)
X		putc('\t', fd);
X	    fprintf(fd, "/*%3d\t*/\n", hval);
X	    last = hval + 1;
X	}
X	fprintf(fd, "};\n");
X	for (funp = function; *funp != NULL; funp++)
X	    fprintf(fd, "%s\n", *funp);
X	fclose(fd);
X}
X
X#if	DOALARM
X/*
X * status - on signal this reports the current statistics
X */
X
XVOID
Xstatus()
X{
X	fprintf(stderr,
X	    "\nSTATUS:  key \"%s\" (%d), search calls = %ld, max depth = %d\n",
X	    keywds[k_now]->word, k_now, bigcount, depth);
X	fflush(stderr);
X	signal(SIGTERM,status);
X	signal(SIGALRM,status);
X	alarm(atime);
X}
X#endif
X
X/*
X *			G E T O P T I O N S
X *
X * Generalized command line argument processor.  The following
X * types of arguments are parsed:
X *	flags		The associated int global is incremented:
X *			-f	f-flag set to 1
X *			-f123	f-flag set to 123 (no separator)
X *			-fg	f-flag and g-flag incremented.
X *	values		A value must be present.  The associated
X *			int global receives the value:
X *			-v123	value set to 123
X *			-v 123	value set to 123
X *	arguments	The associated global (a char *) is
X *			set to the next argument:
X *			-f foo	argument set to "foo"
X */
X
X#define	FLAG	0
X#define	VALUE	1
X#define	ARG	2
X#define	ERROR	3
X
Xtypedef struct argstruct {
X	char	opt;		/* Option byte			*/
X	char	type;		/* FLAG/VALUE/ARG		*/
X	char	*name;		/* What to set if option seen	*/
X	char	*what;		/* String for error message	*/
X} ARGSTRUCT;
X
Xstatic ARGSTRUCT arginfo[] = {
X{ 'd',	FLAG,	(char *)&debug,		"debug" },
X{ 'a',	VALUE,	(char *)&atime,		"alarm time for status" },
X{ 't',	VALUE,	(char *)&tlimit,	"table size limit" },
X{ 'v',	VALUE,	(char *)&vlimit,	"associated value limit" },
X{ 'k',	VALUE,	(char *)&keylimit,	"keyword limit" },
X{ 'n',	FLAG,	(char *)&nosort,	"no sort wanted" },
X{ 'o',	ARG,	(char *)&output,	"parser output file" },
X{ EOS,	ERROR,	NULL,			NULL },
X};
X
Xstatic char *argtype[] = {
X	"flag", "takes value", "takes argument"
X};
X
Xstatic
Xgetoptions(argc, argv)
Xint		argc;
Xchar		**argv;
X/*
X * Process arg's
X */
X{
X	register char		*ap;
X	register int		c;
X	register ARGSTRUCT	*sp;
X	int			i;
X	int			helpneeded;
X
X	getredirection(argc, argv);
X	helpneeded = FALSE;
X	for (i = 1; i < argc; i++) {
X	    if ((ap = argv[i]) != NULL && *ap == '-') {
X		argv[i] = NULL;
X		for (ap++; (c = *ap++) != EOS;) {
X		    if (isupper(c))
X			c = tolower(c);
X		    sp = arginfo;
X		    while (sp->opt != EOS && sp->opt != c)
X			sp++;
X		    switch (sp->type) {
X		    case FLAG:			/* Set the flag	*/
X			if (!isdigit(*ap)) {
X			    (*((int *)sp->name))++;
X			    break;
X			}
X		    case VALUE:			/* -x123	*/
X		        if (isdigit(*ap)) {
X			    *((int *)sp->name) = atoi(ap);
X			    *ap = EOS;
X			}
X			else if (*ap == EOS && ++i < argc) {
X			    *((int *)sp->name) = atoi(argv[i]);
X			    argv[i] = NULL;
X			}
X			else {
X			    fprintf(stderr,
X				"Bad option '%c%s' (%s)",
X				c, ap, sp->what);
X			    fprintf(stderr, ", ignored\n");
X			    helpneeded++;
X			}
X			break;
X
X		    case ARG:			/* -x foo	*/
X			if (++i < argc) {
X			    *((char **) sp->name) = argv[i];
X			    argv[i] = NULL;
X			}
X			else {
X			    fprintf(stderr,
X				"Argument needed for '%c' (%s)",
X				c, sp->what);
X			    fprintf(stderr, ", ignored\n");
X			    helpneeded++;
X			}
X			break;
X
X		    case ERROR:
X			fprintf(stderr,
X			    "Unknown option '%c', ignored\n", c);
X			helpneeded++;
X			break;
X		    }
X		}
X	    }
X	}
X	if (helpneeded > 0) {
X	    for (sp = arginfo; sp->opt != EOS; sp++) {
X		fprintf(stderr, "'%c' -- %s (%s)\n",
X		    sp->opt, sp->what, argtype[sp->type]);
X	    }
X	}
X}
X
X/*
X * getredirection() is intended to aid in porting C programs
X * to VMS (Vax-11 C) which does not support '>' and '<'
X * I/O redirection.  With suitable modification, it may
X * useful for other portability problems as well.
X */
X
X#include	<stdio.h>
X
Xgetredirection(argc, argv)
Xint		argc;
Xchar		**argv;
X/*
X * Process vms redirection arg's.  Exit if any error is seen.
X * If getredirection() processes an argument, argv[i], it is changed
X * to NULL.
X *
X * Warning: do not try to simplify the code for vms.  The code
X * presupposes that getredirection() is called before any data is
X * read from stdin or written to stdout.
X *
X * Normal usage is as follows:
X *
X *	main(argc, argv)
X *	int		argc;
X *	char		*argv[];
X *	{
X *		register int		i;
X *		int			nargs;
X *
X *		getredirection(argc, argv);	** setup redirection
X *		for (nargs = 0, i = 1; i < argc, i++) {
X *		    if (argv[i] == NULL)	** skip if processed
X *			continue;		** by getredirection()
X *		    nargs++;			** here is an argument
X *		    ...				** process argv[i]
X *		}
X *		if (nargs == 0) {		** no arguments given
X *		    ...
X *		}
X *	}
X */
X{
X#ifdef	vms
X	register char		*ap;	/* Argument pointer	*/
X	int			i;	/* argv[] index		*/
X	int			file;	/* File_descriptor 	*/
X	extern int		errno;	/* Last vms i/o error 	*/
X
X	for (i = 1; i < argc; i++) {	/* Do all arguments	*/
X	    if (*(ap = argv[i]) == '<') {  /* <file		*/
X		if (freopen(++ap, "r", stdin) == NULL) {
X		    perror(ap);		/* Can't find file	*/
X		    exit(errno);	/* Is a fatal error	*/
X		}
X		goto erase_arg;		/* Ok, erase argument	*/
X	    }
X	    else if (*ap++ == '>') {	/* >file or >>file	*/
X		if (*ap == '>') {	/* >>file		*/
X		    /*
X		     * If the file exists, and is writable by us,
X		     * call freopen to append to the file (using the
X		     * file's current attributes).  Otherwise, create
X		     * a new file with "vanilla" attributes as if
X		     * the argument was given as ">filename".
X		     * access(name, 2) is TRUE if we can write on
X		     * the specified file.
X		     */
X		    if (access(++ap, 2) == 0) {
X			if (freopen(ap, "a", stdout) == NULL) {
X			    perror(ap);
X			    exit(errno);
X			}
X			else goto erase_arg;
X		    }			/* If file accessable	*/
X		    else ;		/* Else it's just >file	*/
X		}
X		/*
X		 * On vms, we want to create the file using "standard"
X		 * record attributes.  create(...) creates the file
X		 * using the caller's default protection mask and
X		 * "variable length, implied carriage return"
X		 * attributes. dup2() associates the file with stdout.
X		 */
X		if ((file = creat(ap, 0, "rat=cr", "rfm=var")) == -1
X		 || dup2(file, fileno(stdout)) == -1) {
X		    perror(ap);		/* Can't create file	*/
X		    exit(errno);	/* is a fatal error	*/
X		}			/* If '>' creation	*/
Xerase_arg:	argv[i] = NULL;		/* red. erases argument	*/
X	    }				/* If redirection	*/
X	}				/* For all arguments	*/
X#endif
X#ifdef	decus
X	argc = argv[0];			/* Supress warning msg.	*/
X#endif
X}
X
X#if	UNIX
X/*
X * The following is missing on some Unix systems
X */
X
Xchar *
Xstrchr(string, c)
Xregister char	*string;
Xregister char	c;
X/*
X * If 'c' is in string, return a pointer to it.
X * Else, return NULL.
X */
X{
X	do {
X	    if (*string == c)
X		return (string);
X	} while (*string++ != EOS);
X	return (NULL);
X}
X#endif
END_OF_FILE
if test 29699 -ne `wc -c <'perf.c'`; then
    echo shar: \"'perf.c'\" unpacked with wrong size!
fi
# end of 'perf.c'
fi
echo shar: End of shell archive.
exit 0